package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No77组合 {

    /**
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     *
     * 示例:
     * 输入: n = 4, k = 2
     * 输出:
     * [
     *   [2,4],
     *   [3,4],
     *   [2,3],
     *   [1,2],
     *   [1,3],
     *   [1,4],
     * ]
     */

    List<List<Integer>> lists=new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        dg(n,k,1,new ArrayDeque<>());
        return lists;
    }

    private void dg(int n, int k,int start,Deque<Integer> stack){

//        if(stack.size()>k)
//            return;
        if(stack.size()==k){
            lists.add(new ArrayList<>(stack));
            return;
        }

        //不再调用栈去return;for判断这里可以继续优化优化,无需遍历完毕,跳过最后几个无法发展成结果的遍历
        //i < n-(k-stack.size())+1+1;
        for (int i = start; i < n-(k-stack.size())+1+1; i++) {
            stack.addLast(i);
            dg(n,k,i+1,stack);
            stack.removeLast();
        }

    }

    public static void main(String[] args) {
        No77组合 n=new No77组合();
        List<List<Integer>> combine = n.combine(4, 2);
        System.out.println(JSON.toJSONString(combine));
    }

}
